package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月16日
*时间：上午11:22:15
*/
public class Q192 {
    /**
     * @param s: A string 
     * @param p: A string includes "?" and "*"
     * @return: A boolean
     */
    public boolean isMatch(String s, String p) {
        if (s == null) {
            return p == null;
        }
        if (s.equals(p)) {
            return true;
        }
        if ("*".equals(p)) {
            return true;
        }
        int n = s.length();
        int m = p.length();
        boolean dp[][] = new boolean[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char cs = s.charAt(i - 1);
                char cp = p.charAt(j - 1);
                if ('*' == cp) {
                    if (j == 1) {
                        dp[i][j] = true;
                        dp[i - 1][j] = true;
                    } else {
                        dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 1][j];
                    }
                } else if ('?' == cp) {
                    if (j == 1) {
                        if (i == 1) {
                            dp[i][j] = true;
                        }
                    } else {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else if (cs == cp) {
                    if (j == 1) {
                        if (i == 1) {
                            dp[i][j] = true;
                        }
                    } else {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[n][m];
    }

    @Test
    public void testA() {
        System.out.println(isMatch("abc", "a*?bc"));
    }
}
